home *** CD-ROM | disk | FTP | other *** search
/ Ian & Stuart's Australian Mac: Not for Sale / Another.not.for.sale (Australia).iso / hold me in your arms / PGP 2.6 / rsaref Toolkit / source / digit.c < prev    next >
C/C++ Source or Header  |  1992-02-29  |  2KB  |  109 lines
  1. /* DIGIT.C - digit arithmetic routines
  2.  */
  3.  
  4. /* Copyright (C) 1991-2 RSA Laboratories, a division of RSA Data
  5.    Security, Inc. All rights reserved.
  6.  */
  7.  
  8. #include "global.h"
  9. #include "rsaref.h"
  10. #include "nn.h"
  11. #include "digit.h"
  12.  
  13. /* Computes a = b * c, where b and c are digits.
  14.  
  15.    Lengths: a[2].
  16.  */
  17. void NN_DigitMult (a, b, c)
  18. NN_DIGIT a[2], b, c;
  19. {
  20.   NN_DIGIT t, u;
  21.   NN_HALF_DIGIT bHigh, bLow, cHigh, cLow;
  22.  
  23.   bHigh = HIGH_HALF (b);
  24.   bLow = LOW_HALF (b);
  25.   cHigh = HIGH_HALF (c);
  26.   cLow = LOW_HALF (c);
  27.  
  28.   a[0] = (NN_DIGIT)bLow * (NN_DIGIT)cLow;
  29.   t = (NN_DIGIT)bLow * (NN_DIGIT)cHigh;
  30.   u = (NN_DIGIT)bHigh * (NN_DIGIT)cLow;
  31.   a[1] = (NN_DIGIT)bHigh * (NN_DIGIT)cHigh;
  32.   
  33.   if ((t += u) < u)
  34.     a[1] += TO_HIGH_HALF (1);
  35.   u = TO_HIGH_HALF (t);
  36.   
  37.   if ((a[0] += u) < u)
  38.     a[1]++;
  39.   a[1] += HIGH_HALF (t);
  40. }
  41.  
  42. /* Sets a = b / c, where a and c are digits.
  43.  
  44.    Lengths: b[2].
  45.    Assumes b[1] < c and HIGH_HALF (c) > 0. For efficiency, c should be
  46.    normalized.
  47.  */
  48. void NN_DigitDiv (a, b, c)
  49. NN_DIGIT *a, b[2], c;
  50. {
  51.   NN_DIGIT t[2], u, v;
  52.   NN_HALF_DIGIT aHigh, aLow, cHigh, cLow;
  53.  
  54.   cHigh = HIGH_HALF (c);
  55.   cLow = LOW_HALF (c);
  56.  
  57.   t[0] = b[0];
  58.   t[1] = b[1];
  59.  
  60.   /* Underestimate high half of quotient and subtract.
  61.    */
  62.   if (cHigh == MAX_NN_HALF_DIGIT)
  63.     aHigh = HIGH_HALF (t[1]);
  64.   else
  65.     aHigh = (NN_HALF_DIGIT)(t[1] / (cHigh + 1));
  66.   u = (NN_DIGIT)aHigh * (NN_DIGIT)cLow;
  67.   v = (NN_DIGIT)aHigh * (NN_DIGIT)cHigh;
  68.   if ((t[0] -= TO_HIGH_HALF (u)) > (MAX_NN_DIGIT - TO_HIGH_HALF (u)))
  69.     t[1]--;
  70.   t[1] -= HIGH_HALF (u);
  71.   t[1] -= v;
  72.  
  73.   /* Correct estimate.
  74.    */
  75.   while ((t[1] > cHigh) ||
  76.          ((t[1] == cHigh) && (t[0] >= TO_HIGH_HALF (cLow)))) {
  77.     if ((t[0] -= TO_HIGH_HALF (cLow)) > MAX_NN_DIGIT - TO_HIGH_HALF (cLow))
  78.       t[1]--;
  79.     t[1] -= cHigh;
  80.     aHigh++;
  81.   }
  82.  
  83.   /* Underestimate low half of quotient and subtract.
  84.    */
  85.   if (cHigh == MAX_NN_HALF_DIGIT)
  86.     aLow = LOW_HALF (t[1]);
  87.   else
  88.     aLow =
  89.       (NN_HALF_DIGIT)
  90.         ((NN_DIGIT)(TO_HIGH_HALF (t[1]) + HIGH_HALF (t[0])) / (cHigh + 1));
  91.   u = (NN_DIGIT)aLow * (NN_DIGIT)cLow;
  92.   v = (NN_DIGIT)aLow * (NN_DIGIT)cHigh;
  93.   if ((t[0] -= u) > (MAX_NN_DIGIT - u))
  94.     t[1]--;
  95.   if ((t[0] -= TO_HIGH_HALF (v)) > (MAX_NN_DIGIT - TO_HIGH_HALF (v)))
  96.     t[1]--;
  97.   t[1] -= HIGH_HALF (v);
  98.  
  99.   /* Correct estimate.
  100.    */
  101.   while ((t[1] > 0) || ((t[1] == 0) && t[0] >= c)) {
  102.     if ((t[0] -= c) > (MAX_NN_DIGIT - c))
  103.       t[1]--;
  104.     aLow++;
  105.   }
  106.   
  107.   *a = TO_HIGH_HALF (aHigh) + aLow;
  108. }
  109.